#define DEBUG
#include <cstdio>
#include <cmath>

using namespace std;

const int maxn=5000000, mods=998244353;

void calcDivisor(long long x, long long divisor[2]) {
  for (int i=2; i<=sqrt(x); i++) {
    int t=0;
    for (; x%i==0; x/=i) {
      t++;
    }
    if (t) {
      divisor[t-1]++;
    }
  }
  if (x>1) {
    divisor[0]++;
  }
}

long long qpower(long long a, long long n) {
  if (!n) {
    return 1;
  }
  long long s=1;
  for (; n>1; n/=2) {
    if (n%2) {
      s = s*a%mods;
    }
    a = a*a%mods;
  }
  return a*s%mods;
}

int main() {
  freopen("pj.in", "r", stdin);
  freopen("pj.out", "w", stdout);

  static long long f[maxn+1], fact[maxn+1], divisor[2];

  int t;
  long long x;
  scanf("%lld %d", &x, &t);

  fact[0] = fact[1] = f[0] = f[1] = 1;
  for (long long i=2; i<=maxn; i++) {
    f[i] = (i*i%mods*f[i-1]%mods+mods-i*(i-1)/2%mods*(i-1)%mods*f[i-2]%mods)%mods;
    fact[i] = fact[i-1]*i%mods;
  }
  calcDivisor(x, divisor);

  for (int ti=1; ti<=t; ti++) {
    long long n;
    scanf("%lld", &n);
    long long ans=qpower(2, (n-1)*(n-1)%(mods-1))*qpower(fact[n], divisor[0])%mods*qpower(f[n], divisor[1])%mods;
    printf("%lld\n", ans);
  }

  fclose(stdin);
  fclose(stdout);
  return 0;
}
